package class05;

import java.util.*;

public class Code03_TreeMaxWidth {

	public static class Node {
		public int value;
		public Node left;
		public Node right;

		public Node(int data) {
			this.value = data;
		}
	}

	public static int getMaxWidth(Node head) {
		if (head == null) {
			return 0;
		}
		int maxWidth = 0;
		int curWidth = 0;
		int curLevel = 0;
		Queue quene = new LinkedList<>();
		quene.isEmpty();
		HashMap<Node, Integer> levelMap = new HashMap<>(); // 记录节点所在层次
		levelMap.put(head, 1);
		LinkedList<Node> queue = new LinkedList<>();
		queue.add(head);
		Node node = null;
		Node left = null;
		Node right = null;
		while (!queue.isEmpty()) {
			node = queue.poll();
			left = node.left;
			right = node.right;
			if (left != null) {
				levelMap.put(left, levelMap.get(node) + 1);
				queue.add(left);
			}
			if (right != null) {
				levelMap.put(right, levelMap.get(node) + 1);
				queue.add(right);
			}
			if (levelMap.get(node) > curLevel) {
				curWidth = 0;
				curLevel = levelMap.get(node);
			} else {
				curWidth++;
			}
			maxWidth = Math.max(maxWidth, curWidth);
		}
		return maxWidth;
	}

	public int maxWidth2(Node h)
	{
		if(h == null) return 0;
		Queue<Node> queue = new LinkedList<>();
		queue.add(h);

		int curlevelNodes = 0;    //当前行数所有的节点个数
		int max = 0;              //目前为止一行中最多节点的个数
		Node levelEnd = h;        //当前行的尾节点
		Node nextEnd = null;      //下一行的尾节点

		while(!queue.isEmpty())
		{
			Node cur = queue.poll();
			curlevelNodes++;
			if(cur.left != null)//如果左孩子存在
			{
				queue.add(cur.left);//入队
				nextEnd = cur.left; //更新下一行的尾节点
			}
			if(cur.right != null)//同上
			{
				queue.add(cur.right);
				nextEnd = cur.right;
			}
			if(cur == levelEnd)  //到达尾节点，此时改行的节点的左右子树都已入队，nextEnd也更新到最后
			{
				//即将进入新的一行，更新levelEnd = nextEnd
				//并结算和清空curlevelNodes
				levelEnd = nextEnd;
				max = Math.max(max,curlevelNodes);
				curlevelNodes = 0;
			}

		}
		return max;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

}
